//
//  ListQA.swift
//  Swift刷算法
//
//  Created by 卢悦明 on 2020/12/25.
//
import Foundation

class ListQA: NSObject {

    static func QA() {
//        print("*******************************翻转")
//        ReverseList.QA()
//        print("*******************************删除节点")
//        DeleteNode.QA()
//        print("*******************************环形链表")
//        HasCycle.QA()
//        print("*******************************移除链表元素")
//        RemoveElements.QA()
//        print("*******************************双向链表")
//        let doubleList = DoubleLinkedList<Int>();
//        doubleList.creatList([0])
//        doubleList.printList()
//        doubleList.add(1, value: 1)
//        doubleList.printList()
//        print("*******************************单向循环链表")
//        var cycle:SingleCycleLinkedList<Int> = SingleCycleLinkedList();
//        cycle.creatList(array: [])
//        cycle.add(0, value: 0)
//        cycle.add(1, value: 1)
//        cycle.add(2, value: 3)
////        cycle.add(2, value: 2)
//
//        let value = cycle.remove(2)
//        cycle.remove(0)
//
//        print("------", value ?? 10000)
//        cycle.printList()
        
        var list1 = LinkedList<Int>()
        let node1 = list1.creatList(array: [4,2,1,3])
        let result = sortList(node1)
        LinkedList.printList(result)
    }
    
    static func sortList(_ head: ListNode<Int>?) -> ListNode<Int>? {
        guard let head = head else {
            return head
        }
        var array = [ListNode<Int>]()
        var current: ListNode<Int>? = head
        while let temp = current {
            array.append(temp)
            current = temp.next
        }
        array.sort {
            $0.val < $1.val
        }
        array.forEach { item in
            print(item.val)
        }
        
        let newHeader = ListNode<Int>(-1)
        var curr = newHeader
        for node in array {
            curr.next = node
            curr = node
        }
        curr.next = nil
        return newHeader.next
    }
    /// 虚拟头节点
    static func removeElements(_ head: ListNode<Int>?, _ val: Int) -> ListNode<Int>? {
        if head == nil {
            return nil
        }
        let newHeader = ListNode(0)
        var newTail = newHeader
        var tempHeader = head
        while tempHeader != nil {
            if tempHeader!.val != val {
                newTail.next = tempHeader
                newTail = tempHeader!
            }
            tempHeader = tempHeader!.next
        }
        newTail.next = nil
        return newHeader.next
    }
    
    
}
